﻿#define  _CRT_SECURE_NO_WARNINGS
//输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
//
//假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* BuyNode(int x)
{
    struct TreeNode* newnode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    newnode->val = x;
    newnode->left = NULL;
    newnode->right = NULL;

    return newnode;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, 
    int* inorder, int inorderSize) {
    if (preorderSize == 0 || inorderSize == 0)
        return NULL;

    struct TreeNode* root = BuyNode(preorder[0]);
    int i = 0;
    for (i = 0;i < inorderSize;i++)
    {
        if (inorder[i] == preorder[0])
            break;
    }
    root->left = buildTree(&preorder[1], i, &inorder[0], i);
    root->right = buildTree(&preorder[i + 1], preorderSize - i - 1, 
        &inorder[i + 1], inorderSize - i - 1);

    return root;

}
//请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
//
//例如，二叉树 [1, 2, 2, 3, 4, 4, 3] 是对称的。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool judge(struct TreeNode* left, struct TreeNode* right)
{
    if (right == NULL && left == NULL)
        return true;

    if (right == NULL || left == NULL)
        return false;

    if (left->val != right->val)
        return false;

    return judge(left->left, right->right) && judge(left->right, right->left);

}

bool isSymmetric(struct TreeNode* root) {
    if (root == NULL)
        return true;
    return judge(root->left, root->right);
}
